package calculator;

import java.text.DecimalFormat;
import java.util.*;

/**
 * The class implements the Calculator interface.
 * Calculation is based on reverse Polish notation (RPN) (also known as postfix notation).
 *
 * @author Andrey Murgo
 */
public class CalculatorImpl implements Calculator {
    @Override
    public String evaluate(String statement) {
        String out;
        try {
            List items = parseStatement(statement);
            items = toPostfixNotation(items);
            double res = polishCalc(items);
            /*Rounding the result.*/
            DecimalFormat df = new DecimalFormat("#.####");
            out = df.format(res).replace(',', '.');
        } catch (Exception e) {
            out = null;
        }
        return out;
    }

    /**
     * This method parses the specified statement.
     *
     * @param statement mathematical statement containing digits, '.' as decimal mark,
     *                  parentheses, operations signs '+', '-', '*', '/'
     * @return mathematical statement represented as a list of ArithmeticItems
     * @throws IllegalArgumentException if statement is empty or contains illegal elements
     */
    private List parseStatement(String statement) throws IllegalArgumentException {
        if (statement.length() == 0) {
            throw new IllegalArgumentException("The statement is empty");
        }
        List<Object> list = new ArrayList<Object>(statement.length());

        /*Parentheses and operations signs are used to split the statement*/
        StringTokenizer stringTokenizer = new StringTokenizer(statement, "\\+|\\-|/|\\*|\\)|\\(", true);
        String arg;
        boolean onlyUnary = true; //this flag is used to find an unary operation
        while (stringTokenizer.hasMoreTokens()) {
            arg = stringTokenizer.nextToken().trim();
            try {
                double x = Double.parseDouble(arg);
                list.add(x);
                onlyUnary = false;
            } catch (NumberFormatException e) {
               /* if argument is not numeric type*/
                if ("+".equals(arg)) {
                    if (onlyUnary) {
                        list.add(Operation.UN_PLUS);
                    } else {
                        list.add(Operation.ADD);
                    }
                    onlyUnary = true;
                } else if ("-".equals(arg)) {
                    if (onlyUnary) {
                        list.add(Operation.UN_MINIS);
                    } else {
                        list.add(Operation.SUB);
                    }
                    onlyUnary = true;
                } else if ("/".equals(arg)) {
                    list.add(Operation.DIV);
                    onlyUnary = true;
                } else if ("*".equals(arg)) {
                    list.add(Operation.MUL);
                    onlyUnary = true;
                } else if (")".equals(arg)) {
                    list.add(Parenthesis.RIGHT);
                    onlyUnary = false;
                } else if ("(".equals(arg)) {
                    list.add(Parenthesis.LEFT);
                    onlyUnary = true;
                } else {
                    throw new IllegalArgumentException("Illegal element: " + arg);
                }
            }
        }
        return list;
    }

    /**
     * This method uses the shunting-yard algorithm to convert infix expressions
     * to postfix.
     *
     * @param inputList mathematical statement represented as a list of ArithmeticItems
     * @return input list in postfix order
     * @throws IllegalArgumentException if there are mismatched parentheses in the input statement
     */
    private List toPostfixNotation(List inputList) throws IllegalArgumentException {

        List<Object> outputList = new ArrayList<Object>(inputList.size());
        LinkedList<Object> stack = new LinkedList<Object>();

        for (Object currentItem : inputList) {
            switch (getItemType(currentItem)) {
                case OPERAND:
                    outputList.add(currentItem);
                    break;
                case PARENTHESIS:
                    if (currentItem == Parenthesis.LEFT) {
                        stack.push(currentItem);
                    } else {
                        try {
                            while (true) {
                                Object stackTop = stack.getFirst();
                                if (isParenthesis(stackTop)) {
                                    if (stackTop == Parenthesis.LEFT) {
                                        break;
                                    }
                                }
                                outputList.add(stack.pop());
                            }
                            stack.pop(); //delete the left parenthesis from the stack
                        } catch (NoSuchElementException e) {
                        /*If the stack runs out without finding a left parenthesis*/
                            throw new IllegalArgumentException("There are mismatched parentheses in the statement");
                        }
                    }
                    break;
                case OPERATION:
                    Operation currentOperation = (Operation)currentItem;
                    boolean isOperationOnStackTop;
                    int stackTopOperationPrecedence;
                    int currentOperationPrecedence;
                    while (true) {
                        isOperationOnStackTop = (!stack.isEmpty() && isOperation(stack.getFirst()));
                        if (isOperationOnStackTop) {
                            Operation stackTopOperation = (Operation) stack.getFirst();
                            stackTopOperationPrecedence = stackTopOperation.getPrecedence();
                            currentOperationPrecedence = currentOperation.getPrecedence();
                            if ((!currentOperation.isRight() && (currentOperationPrecedence == stackTopOperationPrecedence))
                                    || (currentOperationPrecedence < stackTopOperationPrecedence)) {
                                outputList.add(stack.pop());
                            } else {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    stack.push(currentItem);
                    break;
                default:
                    throw new IllegalArgumentException("The expression has illegal items");
            }
        }
        for (Object stackItem : stack) {
            if (isOperation(stackItem)) {
                outputList.add(stackItem);
            } else {
                throw new IllegalArgumentException("There are mismatched parentheses in the statement");
            }
        }
        return outputList;
    }

    /**
     * This method evaluates a postfix expression
     *
     * @param postfixExpression a postfix expression
     * @return result of evaluation
     * @throws IllegalArgumentException if the expression has incorrect number of operands
     */
    private double polishCalc(List postfixExpression) throws IllegalArgumentException {
        final ArithmeticStack stack = new ArithmeticStack();
        for (Object arg : postfixExpression) {
            switch (getItemType(arg)) {
                case OPERAND:
                    Double operand = (Double) arg;
                    stack.push(operand);
                    break;
                case OPERATION:
                    try {
                        Operation operation = (Operation) arg;
                        stack.execute(operation);
                    } catch (NoSuchElementException e1) {
                        throw new IllegalArgumentException("The expression has not enough operands");
                    }
                    break;
                default:
                    throw new IllegalArgumentException("The expression has illegal items");
            }
        }
        double res = stack.pop();
        if (!stack.isEmpty()) {
            throw new IllegalArgumentException("The expression has too many operands");
        }
        return res;
    }

    private boolean isOperation(Object element) {
        return (element instanceof Operation);
    }

    private boolean isParenthesis(Object element) {
        return (element instanceof Parenthesis);
    }

    private ItemType getItemType(Object element) {
        if (element instanceof Operation) {
            return ItemType.OPERATION;
        } else if (element instanceof Parenthesis) {
            return ItemType.PARENTHESIS;
        } else if (element instanceof Double) {
            return ItemType.OPERAND;
        } else
            return ItemType.UNKNOWN;
    }
}

/**
 * This class is used for performing numeric operations when a
 * postfix expression is evaluated.
 */
class ArithmeticStack extends LinkedList<Double> {

    /**
     * This method executes the operation specified by the argument
     *
     * @param op an operation (ADD, SUM, DIV, MUL, UN_MINUS or UN_PLUS)
     * @throws NoSuchElementException if stack has not enough operands
     * @throws ArithmeticException    if the result is NaN or an infinity
     */
    public void execute(Operation op) throws NoSuchElementException, ArithmeticException {
        double x;
        double y;
        double res = 0;

        if (op.isUnary()) {
            x = pop();
            switch (op) {
                case UN_MINIS:
                    res = -x;
                    break;
                case UN_PLUS:
                    res = x;
                    break;
            }
        } else {
            x = pop();
            y = pop();
            switch (op) {
                case ADD:
                    res = x + y;
                    break;
                case SUB:
                    res = y - x;
                    break;
                case MUL:
                    res = x * y;
                    break;
                case DIV:
                    res = y / x;
                    break;
            }
        }
        if (Double.isInfinite(res)) {
            throw new ArithmeticException("Result is an infinity");
        } else if (Double.isNaN(res)) {
            throw new ArithmeticException("Result is not a number");
        } else {
            push(res);
        }
    }
}

enum Operation {
    ADD(1, false, false),
    SUB(1, false, false),
    MUL(2, false, false),
    DIV(2, false, false),
    UN_MINIS(3, true, true),
    UN_PLUS(3, true, true);

    private final int precedence;   // operation precedence
    private final boolean isUnary;  // true - unary operation; false - binary
    private final boolean isRight;  // true if the operation is right-associative

    Operation(int priority, boolean isUnary, boolean isRight) {
        this.precedence = priority;
        this.isUnary = isUnary;
        this.isRight = isRight;
    }

    public int getPrecedence() {
        return precedence;
    }

    public boolean isUnary() {
        return isUnary;
    }

    public boolean isRight() {
        return isRight;
    }
}

enum ItemType {
    UNKNOWN,
    OPERATION,
    OPERAND,
    PARENTHESIS
}

enum Parenthesis {
    LEFT,
    RIGHT
}




